package 递归.二分搜索树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BST <E extends Comparable<E>> {
    private class Node{
        E val;
        Node left, right;

        public Node(E val) {
            this.val = val;
            left = null;
            right = null;
        }
    }
    private Node root;
    private int size ;

    public BST() {
        this.root = null;
        this.size = 0;
    }
    public void addR(E e){
        root = addR(root, e);
    }

    /*递归添加*/
    public Node addR(Node node, E e){
        if (node == null){
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.val) < 0)
            node.left = addR(node.left, e);
        else if (e.compareTo(node.val) > 0)
            node.right = addR(node.right, e);
        return node;
    }
    /*非递归添加*/
    public void add( E e){
        if (root == null){
            root = new Node(e);
            size++;
            return ;
        }
        Node cur = root;
        while (cur != null){
            if (e.compareTo(cur.val)<0){
                if (cur.left != null){
                    cur = cur.left;
                }else {
                    cur.left = new Node(e);
                    size++;
                    return;
                }
            }else if (e.compareTo(cur.val)>0 ){
               if ( cur.right == null){
                   cur.right = new Node(e);
                   size++;
                   return;
                }else {
                   cur = cur.right;
                }
            } else return;
        }



    }
    /*递归查询e*/
    public boolean contains(E e){
        return contains(root, e);
    }
    public boolean contains(Node node, E e){
        if (node == null){
            return false;
        }
        if (node.val.compareTo(e) == 0){
            return true;
        }
        else if (node.val.compareTo(e) > 0)
            return contains(node.left, e);
        else
            return contains(node.right, e);

    }
    /*递归遍历*/
    public void prePrint(Node node){
        if (node == null)
            return;
        System.out.print(node.val +" " );
        prePrint(node.left);
        prePrint(node.right);
    }
    /*非递归遍历*/
    public void prePrintR(Node node){
        if (node == null)
            return;
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()){
            Node out = stack.pop();
            System.out.print(out.val + " ");
            if (out.right != null){
                stack.push(out.right);
            }
            if (out.left != null){
                stack.push(out.left);
            }
        }
    }
    /*层次遍历*/
    public void levelPrint(Node node){
        if (node == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        Node head = node;
        queue.offer(head);
        while (!queue.isEmpty()){
            Node poll = queue.poll();
            System.out.print(poll.val + " ");
            if (poll.left != null){
                queue.offer(poll.left);
            }
            if (poll.right != null){
                queue.offer(poll.right);
            }

        }

    }
    /*返回最小值*/
    public E getMin(){
       return getMin(root).val;
    }
    public Node getMin(Node node){
        if (node.left == null){
            return node;
        }
        return getMin(node.left);
    }
    /*返回最大值*/
    public E getMax(){
        return getMax(root).val;
    }
    public Node getMax(Node node){
        if (node.right == null){
            return node;
        }
        return getMax(node.right);
    }
    /*删除最小值*/
    public void deleteMin(){
       root = deleteMin(root);
    }
    /*删除最小值*/
    public Node deleteMin(Node node){
        if (node.left == null){
            size--;
            Node rightNode = node.right;
            node.right = null;
            return rightNode;
        }
        node.left = deleteMin(node.left);
        return node;
    }
    /*删除最大值*/
    public void deleteMax(){
       root = deleteMax(root);
    }
    /*删除最大值*/
    public Node deleteMax(Node node){
        if (node.right == null){
            size--;
            Node leftNode = node.left;
            node.left = null;
            return leftNode;
        }
        node.right = deleteMax(node.right);
        return node;
    }
    /*删除任意结点*/
    public void delete(E e){
        root = delete(root, e);
    }
    private Node delete(Node node, E e){
        if (node == null){
            return null;
        }
        /*左子树递归*/
        if (node.val.compareTo(e) > 0){
            node.left =  delete(node.left, e);
            return node;
        }
        /*右子树递归*/
        else if (node.val.compareTo(e) < 0){
            node.right =  delete(node.right, e);
            return node;
        }else
            /*找到要删除的*/
            {
                /*只有右子树*/
            if (node.left == null){
                Node rightNode = node.right;
                size--;
                node.right = null;
                return rightNode;
                /*只有左子树*/
            }else if(node.right == null){
                Node leftNode = node.left;
                size--;
                node.left = null;
                return leftNode;
            }else
                /*左右子树都不为空*/{
                /*找到右子树最小值节点*/
                Node newNode = getMin(node.right);
                /*新节点的右子树等于删除右子树最小值后的树*/
                newNode.right = deleteMin(node.right);
                /*新节点的左子树等于node的左子树*/
                newNode.left = node.left;
                /*删除node*/
                node.left = node.right = null;
                return newNode;
            }
        }

    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        genBSTString(root, 0, res);
        return res.toString();
    }
    private void genBSTString(Node node, int depth, StringBuilder res) {
        if(node == null){
            res.append(genDepthString(depth)+"null\n");
            return;
        }
        res.append(genDepthString(depth)+node.val+"\n");
        genBSTString(node.left, depth+1, res);
        genBSTString(node.right, depth+1, res);

    }
    private String  genDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");

        }
        return res.toString();
    }

    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        Integer []a = {5,3,6,8,4,2};
        for (int i = 0; i < a.length; i++) {
            bst.addR(a[i]);
        }
        for (int i = 0; i < a.length; i++) {
            bst.delete(a[i]);
            System.out.println();
            bst.levelPrint(bst.root);
        }
        System.out.println("===");


    }


}
